package cn.kuick.match3.test3;

import java.util.Stack;

/**
 * 
 * @author 春凡
 *
 * 3、栈的push、pop序列
 * 题目：输入两个整数序列A和B。其中一个序A列表示栈的push顺序，判断另一个序列B有没有可能是对应的pop顺序，如果是，请输出顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。 
 * 示例：
 * 1）输入的push序列A是1、2、3、4、5，pop序列B是4、5、3、2、1，那么序列B就是一个可能pop序列，因为可以有如下的push和pop序列：
 * push 1，push 2，push 3，push 4，pop4，push 5，pop 5，pop 3，pop 2，pop 1
 */
public class PushPopSequence_fan {

	public static void main(String[] args) {
//		pushPop(new Integer[]{1,2,3,4,5}, new Integer[]{4,5,3,2,1}); 
//		pushPop(new Integer[]{1,3,5,4,6}, new Integer[]{3,4,1,5,6});
		pushPop(new Integer[]{1,2,3,4,5}, new Integer[]{2,1,3,4,5});
	}
	
	private static void pushPop(Integer [] push,Integer [] pop){
		
		//存储已经压入栈的元素
		Stack<Integer> pushStack = new Stack<>();
		
		//存储已经弹出栈的元素
		Stack<Integer> popStack = new Stack<>();
		
		//用来记录压入和弹出栈
		StringBuffer buffer = new StringBuffer();
		
		for (int i = 0; i < pop.length; i++) {
			
			Integer popItem = pop[i]; 
			
			for (int j = 0; j < push.length; j++) { 
				
				Integer pushItem = push[j];
				
				// 如果pushStack 和  popStack 中都不含有pushItem，那么就压入栈
				if(!pushStack.contains(pushItem) && !popStack.contains(pushItem)){
					pushStack.push(pushItem);
					buffer.append("push"+pushItem+"\n"); 
				}
				
				if(!pushStack.isEmpty()){
					//取出栈最顶端的元素（不会从栈中移除该元素）
					Integer peekItem = pushStack.peek();
					
					if(peekItem==popItem){
						//如果pushStack的栈顶的元素等于popItem，弹出pushStack的栈顶的元素
						pushStack.pop();
						//把已经弹出的元素压入popStack，弹出过的元素不能再压入pushStack
						popStack.push(peekItem);
						
						buffer.append("pop"+peekItem+"\n"); 
						
						//找到相同的元素，则需要结束push的循环，不然会一次性把全部元素压入栈
						break;
					}
					
				}
				
			}
		}
		
		if(pushStack.isEmpty()){
			System.out.println(buffer.toString()); 
		}else{
			System.out.println("is not match");
		}
		
	}
}










